package com.xhh.learning.record.algorithm.knapsack;

/**
 * 类名： DP
 * 描述：
 * 作者： Administrator
 * 版本： V1.0
 * 创建时间:  2019/5/24 10:49
 * 最后修改时间:  2019/5/24 10:49
 */
public class DP {

    public static void main(String[] args) {
        String str1 = "mitcmu";
        String str2 = "mtacnu";

        // minDistance(str1, str2, 0, 0, 0);
        int i = minDistanceDP(str1.toCharArray(), 6, str2.toCharArray(), 6);
        System.out.println(i);
    }

    /**
     * 动态规划
     */
    private static int minDistanceDP(char[] t1, int n, char[] t2, int m) {
        int[][] states = new int[n][m];
        // 初始化第一行
        for (int i = 0; i < m; i++) {
            if (t1[i] == t2[0]) {
               states[0][i] = i;
            } else if (i != 0) {
                states[0][i] = states[0][i - 1] + 1;
            } else {
                states[0][i] = 1;
            }
        }

        // 初始化第一列
        for (int j = 0; j < n; j++) {
            if (t2[j] == t1[0]) {
                states[j][0] = j;
            } else if (j != 0) {
                states[j][0] = states[j-1][0] + 1;
            } else {
                states[j][0] = 1;
            }
        }

        // 初始化剩余行
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (t1[i] != t2[j]) {
                    states[i][j] = min(states[i - 1][j] + 1, states[i][j - 1] + 1, states[i - 1][j - 1] + 1);
                } else {
                    states[i][j] = min(states[i - 1][j] + 1, states[i][j - 1] + 1, states[i - 1][j - 1]);
                }
            }
        }

        return states[n-1][m-1];
    }

    private static int min(int x, int y, int z) {
        if (y < x) {
            x = y;
        }

        if (z < x) {
            x = z;
        }
        return x;
    }

    /**
     * 回溯
     * @param str1
     * @param str2
     * @param i
     * @param j
     * @param min
     */
    private static void minDistance(String str1, String str2, int i, int j, int min) {
        if (i == str1.length() || j == str2.length()) {
            if (i == str1.length()) {
                min += (str2.length() - j) ;
            }

            if (j == str2.length()) {
                min += (str1.length() - i) ;
            }
            System.out.println(min);
            return;
        }

        if (str1.charAt(i)==str2.charAt(j)) {
            minDistance(str1, str2, i + 1, j + 1, min);
        }else{
            // str2 增加或str1删除一个字符
            minDistance(str1, str2, i + 1, j, min + 1);
            // str1 增加或str2删除一个字符
            minDistance(str1, str2, i, j+1, min + 1);
            // str1 或 str2替换一个字符
            minDistance(str1, str2, i + 1, j+1, min + 1);
        }
    }







}
